# source:https://leetcode.cn/problems/count-the-number-of-good-subarrays/description/ 滑窗 二刷 一刷 24.8.9
class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        ans = 0
        i, total = 0, 0
        d = defaultdict(int)
        for j, v in enumerate(nums):
            d[v] += 1
            total += d[v]-1
            while total >= k:
                d[nums[i]] -= 1
                total -= d[nums[i]]
                i += 1
            ans += i
        return ans

# source:https://leetcode.cn/submissions/detail/593292364/ 滑窗
class Solution:
    def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
        cnt = 0
        i = 0
        m = 1
        for j, v in enumerate(nums):
            m *= v
            while i <= j and m >= k:
                m //= nums[i]
                i += 1
            cnt += j-i+1
        return cnt

